#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

template <typename T>
class BinarySearchTree
{
	public:
		BinarySearchTree() : m_root(nullptr){}
		~BinarySearchTree();

		bool find(const T & value);
		void insert(const T & value);
		void erase(const T & value);

	protected:
		template <typename T>
		class Node
		{
			public:
				explicit Node(const T & value) : m_key_value(value), m_parent(nullptr), m_left(nullptr), m_right(nullptr){}
				T m_key_value;
				Node * m_parent;
				Node * m_left;
				Node * m_right;
			private:
				Node();
				Node(const Node<T> &);
				Node & operator=(const Node<T> &);
		};

		Node<T> * m_root;
		void destroyBranch(Node<T> * node);
};

template<typename T>
BinarySearchTree<T>::~BinarySearchTree()
{
	if(m_root != nullptr)
		destroyBranch(m_root);
	delete m_root;
}
template<typename T>
void BinarySearchTree<T>::destroyBranch(Node<T> * node)
{
	if(node->m_left != nullptr)
		destroyBranch(node->m_left);
	if(node->m_right != nullptr)
		destroyBranch(node->m_right);
	std::cout << "Deleted " << node->m_key_value << std::endl;
	delete node;
}
template<typename T>
bool BinarySearchTree<T>::find(const T & value)
{
	auto p = m_root;
	while(p != nullptr)
	{
		std::cout << p->m_key_value << std::endl;
		if(p->m_key_value == value)
			return true;
		if(value < p->m_key_value)
			p = p->m_left;
		else
			p = p->m_right;
	}
	return false;
}
template<typename T>
void BinarySearchTree<T>::insert(const T & value)
{
	auto p = m_root;
	Node<T> * prev = nullptr;
	while(p != nullptr)
	{
		std::cout << p->m_key_value << std::endl;
		if(p->m_key_value == value)
			return;
		prev = p;
		if(value < p->m_key_value)
			p =  p->m_left;
		else
			p =  p->m_right;
	}
	p = new Node<T>(value);
	p->m_parent = prev;
}
template<typename T>
void BinarySearchTree<T>::erase(const T & value)
{
	// check if tree is empty
	if(m_root == nullptr)
		return;

	// Find the value
	auto p = m_root;
	auto prev = nullptr;
	while(p != nullptr)
	{
		if(p->m_key_value == value)
		{
			break;
		}
		prev = p;
		if(value < p->m_key_value)
			p = p->m_left;
		else
			p = p->m_right;
	}
	if(p == nullptr)
		return; // Value not found

	// Case 1 : Node is a leaf
	if(p->m_left == nullptr && p->m_right == nullptr)
	{
		delete p;
		p = nullptr;
		return;
	}
	// Case 2 : Node has 1 child
	if(p->left != nullptr)
	{
		auto tmp = p->left;
		delete p;
		p = tmp;
		p->parent = prev;
		return;
	}
	else if(p->m_right != nullptr)
	{
		auto tmp = p->m_right;
		delete p;
		p = tmp;
		p->parent = prev;
		return;
	}
	// Case 3 : Node has 2 childs
	auto next = p->right;
	while(next->m_left != nullptr)
		next = next->m_left;
	//Todo: In order to prevent the tree from getting unbalanced 
	//you could take the max element from the left tree from time to time.
	p->m_key_value = next->m_key_value;
	if(next->m_right != nullptr)
	{
		auto tmp = next->m_right;
		tmp->m_parent = next->m_parent;
		delete next;
	}
}
#endif